package com.atguigu.search;

import java.util.Arrays;
import java.util.Random;

/**
 * @Author : SunFeng
 * @Description: 插值查找算法
 * @Date : 2021/7/8  15:32
 */
public class InsertValSearch {
    public static void main(String[] args) {
        int[] arr = new int[100000];
        for (int i = 0; i < 100000; i++) {
            arr[i] = i * 2 + new Random().nextInt(2);
        }
       System.out.println(Arrays.toString(arr));
        int i = insertValSearch(arr, 0, arr.length - 1, 10);
        System.out.println(i);
    }

    /**
     * 插值查找算法
     * @param array
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static int insertValSearch(int[] array, int left, int right, int findVal) {
        System.out.println("x");
        //  findVal < array[0] || findVal > array[array.length - 1]   必须需要
        if (left > right || findVal < array[0] || findVal > array[array.length - 1]) {
            return -1;
        }
        // 重要的公式
        int mid = left + (right - left) * (findVal - array[left]) / (array[right] - array[left]);
        int midVal = array[mid];
        if (findVal > midVal) {
            return insertValSearch(array, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return insertValSearch(array, left, mid - 1, findVal);
        } else {
            return mid;
        }


    }

}
